//https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/503519637/?envType=study-plan-v2&envId=top-100-liked

#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 找到左边界
       int first = binarySearch(nums,target);
        // 找到右边界（注意：k+1）
       int last = binarySearch(nums,target+1);
        // 若超出数组范围，则证明目标值出现的次数为0，否则，右边界减去左边界即能统计出目标出现的次数
        return (first==nums.size() || nums[first]!=target)? vector<int>{-1,-1}:vector<int>{first,last-1};

    }

    int binarySearch(vector<int>& data, int k){
        // 左右边界
        int l = 0, r = data.size();
        while(l < r){
            // 二分求中点
            int m = l+(r-l)/2;
            if(data[m] >= k)
                r = m;
            else
                l = m+1;
        }
        // 返回左边界
        return l;
    }
};